#include <iostream>
#include <vector>

void Adjust(std::vector<int>& nums, int root, int n)
{
    int parent = root;
    int child = parent * 2 + 1;
    while (child < n)
    {
        if (child < n && nums[child] < nums[child + 1])
            child++;
        if (nums[parent] < nums[child])
            std::swap(nums[parent], nums[child]);
        else
            break;
        parent = child;
        child = parent * 2 + 1;
    }
}

void StSort(std::vector<int>& nums)
{
    int n = nums.size();
    for (int i = (n - 1 - 1) / 2; i >= 0; i--)
    {
        Adjust(nums, i, n);
    }

    for (int i = n - 1; i >= 0; i--)
    {
        std::swap(nums[0], nums[i]);
        Adjust(nums, 0, i);
    }
}

int main()
{
    std::vector<int> nums = { 9, 8, 7, 6, 5, 4, 3, 2, 1 };
    StSort(nums);
    for (auto e : nums)
    {
        std::cout << e << ' ';
    }
    return 0;
}